package main

import (
	"bytes"
	"container/heap"
	"errors"
	"fmt"
	"math"
	"sort"
	"strconv"
	"strings"
)

//605. 种花问题
func CanPlaceFlowers(flowerbed []int, n int) bool {
	// 如果花种完了，或者花床检查完了，都停止遍历
	for i, length := 0, len(flowerbed); i < length && n > 0; {
		if flowerbed[i] == 1 {
			//即如果，当前i位置已经种植了话，那么下一个可以种花的位置是 i+2
			i += 2
		} else if i == length-1 || flowerbed[i+1] == 0 {
			//这里很关键
			//如果是最后一个位置了，那么肯定能够种植（i==flowerbed.length-1)
			//如果不是，则还需要确保 可种花的位置(i+2)紧邻其后的(i+2+1)的位置没有种植（flowerbed[i+1]==0)
			//只有这样才可以种植
			n--
			//同时找出下一个可以种植的位置
			i += 2
		} else {
			//这种情况是flowerbed[i+2+1]=1，所以下次循环就从这里重新开始判断其后可种植的位置
			i += 3
		}
	}
	return n <= 0
}

//594. 最长和谐子序列 (滑动窗口)
//nums = [1,3,2,2,5,2,3,7]
func FindLHS(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	ans := 0
	for i, j := 0, 0; j < n; j++ {
		for i < j && nums[j]-nums[i] > 1 {
			i++
		}
		if nums[j]-nums[i] == 1 {
			ans = max(ans, j-i+1)
		}
	}
	return ans
}

//11. 盛最多水的容器
//[1,8,6,2,5,4,8,3,7]
func MaxArea(height []int) int {

	i, j, res := 0, len(height)-1, 0
	//短板每次向内移动一格
	for i < j {
		if height[i] < height[j] {
			res = max(res, (j-i)*height[i])
			i++
		} else {
			res = max(res, (j-i)*height[j])
			j--
		}
	}
	return res
}

func Min(x, y int) int {
	if x < y {
		return x
	}
	return y
}
func Max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

//187. 重复的DNA序列
func FindRepeatedDnaSequences(s string) []string {
	strMap := make(map[string]int)
	length := len(s)
	var strArr []string

	for i := 0; i <= length-10; i++ {
		tenStr := s[i : i+10]
		strMap[tenStr] += 1
		if strMap[tenStr] == 2 {
			strArr = append(strArr, tenStr)
		}
	}
	return strArr
}

//自己想的结果超时了
func MaxSatisfiedBob(customers []int, grumpy []int, minutes int) int {
	gruMap := make(map[int]int)
	//1.gruMap中记录每次生气时在店内顾客的人数
	for k, v := range grumpy {
		if v == 1 {
			gruMap[k] = customers[k]
		}
	}
	maxLimit, startPos := 0, 0

	for pos, _ := range gruMap {
		temp := 0
		for i := 0; i < minutes; i++ {
			temp += grumpy[pos+i]
		}

		for i := 0; i < minutes; i++ {
			value, ok := gruMap[pos+i]
			if ok {
				temp += value

			}
		}

		if temp > maxLimit {
			maxLimit = temp
			startPos = pos
		}
	}
	for i := 0; i < minutes; i++ {
		if startPos+i < len(grumpy) {
			grumpy[startPos+i] = 0
		}
	}

	result := 0
	for k, v := range grumpy {
		if v == 0 {
			result += customers[k]
		}
	}
	return result

}

//1052:爱生气的书店老板
func MaxSatisfied(customers []int, grumpy []int, minutes int) int {
	ans := 0
	for k, v := range grumpy {
		if v == 0 {
			ans += customers[k]
			customers[k] = 0
		}
	}
	cur, max := 0, 0
	for k, v := range customers {
		cur += v
		if k >= minutes {
			cur -= customers[k-minutes]
		}
		max = Max(max, cur)
	}
	return max + ans
}

func ThreeSum(nums []int) [][]int {
	//1.先给nums排序
	sort.Ints(nums)
	var result [][]int
	length := len(nums)

	for k := 0; k < length-2; k++ {
		if nums[k] > 0 {
			break
		}
		if k > 0 && nums[k] == nums[k-1] {
			continue
		}

		i, j := k+1, length-1
		for i < j {
			sum := nums[k] + nums[i] + nums[j]

			if sum < 0 {
				i++
				for i < j && nums[i] == nums[i-1] {
					i++
				}
			} else if sum > 0 {
				j--
				for i < j && nums[j] == nums[j+1] {
					j--
				}
			} else {
				temp := []int{nums[k], nums[i], nums[j]}
				result = append(result, temp)
				i++
				j--
				for i < j && nums[i] == nums[i-1] {
					i++
				}
				for i < j && nums[j] == nums[j+1] {
					j--
				}

			}
		}
	}
	return result
}

//函数传入可变参数类型
func myFunc(args ...int) {
	for _, arg := range args {
		fmt.Println(arg)
	}
}

func myFunc2(format string, args ...interface{}) {

	for _, arg := range args {
		switch arg.(type) {
		case int:
			fmt.Println(arg, "is an int value.")
		case string:
			fmt.Println(arg, "is a string value.")
		case int64:
			fmt.Println(arg, "is an int64 value.")
		default:
			fmt.Println(arg, "is an unknown type.")
		}
	}
}

func joinStrings(args ...string) string {
	var b bytes.Buffer
	for _, arg := range args {
		b.WriteString(arg)
	}
	return b.String()

}

//todo:怎样调用这个方法呢？
//从切片中删除一个元素
type Slice []int

func (s *Slice) RemoveSlice(value interface{}) error {
	for i, v := range *s {
		if isEqual(value, v) {
			*s = append((*s)[:i], (*s)[i+1:]...)
			return nil
		}
	}
	return errors.New("删除出错")
}

func isEqual(x, y interface{}) bool {
	return x == y
}

//860:柠檬水找零
//5,5,5,10,20
func LemonadeChange(bills []int) bool {

	five, ten := 0, 0
	for _, v := range bills {
		switch v {
		case 5:
			five++
			break
		case 10:
			if five < 1 {
				return false
			}
			five--
			ten++
			break
		case 20:
			//10快有一张5快的没有 10快没有5快的小于三张
			if five > 0 && ten > 0 {
				five--
				ten--
			} else if five >= 3 {
				five -= 3
			} else {
				return false
			}

			break
		}
	}
	return true
}

//888. 公平的糖果交换
//自己想的暴力解法
func fairCandySwapBob(aliceSizes []int, bobSizes []int) []int {
	//1.两数组中相同的值去掉
	sumA, sumB := 0, 0
	for _, v := range aliceSizes {
		sumA += v
	}
	for _, v := range bobSizes {
		sumB += v
	}

	for _, v := range aliceSizes {
		for _, v2 := range bobSizes {
			if v != v2 {
				if sumA-v+v2 == sumB-v2+v {
					return []int{v, v2}
				}

			}

		}
	}
	return []int{}
}

//888. 公平的糖果交换
func fairCandySwap(aliceSizes []int, bobSizes []int) []int {
	var set = map[int]struct{}{}
	sumA, sumB := 0, 0

	for _, x := range aliceSizes {
		sumA += x
		set[x] = struct{}{}
	}
	for _, v := range bobSizes {
		sumB += v
	}
	detal := (sumA - sumB) / 2
	for i := 0; ; i++ {
		y := bobSizes[i]
		x := y + detal
		if _, has := set[x]; has {
			return []int{x, y}
		}
	}
}

//374. 猜数字大小
//利用二分查找
func guessNumber(n int) int {

	left, right := 0, n
	for left < right {
		mid := left + (right-left)/2
		if guess(mid) <= 0 {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

//解题的接口
func guess(num int) int {
	return 0
}

//1160. 拼写单词
func CountCharacters(words []string, chars string) int {
	charMap := make(map[byte]int)
	for _, char := range chars {
		charMap[byte(char)] ++
	}

	total := 0
outLoop:
	for _, word := range words {
		wordMap := make(map[byte]int)
		for _, c := range word {
			wordMap[byte(c)]++
		}
		for k, v := range wordMap {
			if v > charMap[k] {
				continue outLoop
			}
		}
		total += len(word)
	}
	return total
}

//1046. 最后一块石头的重量
//自己想的
func LastStoneWeightBob(stones []int) int {
	BubbleSort2(stones)

	for {
		if len(stones) <= 1 {
			return stones[0]
		}
		i := 0
		if stones[i] == stones[i+1] {
			if len(stones) == 2 {
				return 0
			}
			stones = stones[i+2:]
		} else {
			temp := math.Abs(float64(stones[i] - stones[i+1]))
			stones = stones[i+2:]
			stones = append(stones, int(temp))
		}
		BubbleSort2(stones)

	}
	fmt.Println(stones[0])
	return stones[0]
}

//题解
type hp struct {
	sort.IntSlice
}

func (h hp) Less(i, j int) bool  { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{}   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }
func (h *hp) push(v int)         { heap.Push(h, v) }
func (h *hp) pop() int           { return heap.Pop(h).(int) }

func LastStoneWeight(stones []int) int {
	q := &hp{stones}
	heap.Init(q)
	for q.Len() > 1 {
		x, y := q.pop(), q.pop()
		if x > y {
			q.push(x - y)
		}
	}
	if q.Len() > 0 {
		return q.IntSlice[0]
	}
	return 0
}

func IsBoomerang(points [][]int) bool {
	a, b, c := points[0], points[1], points[2]
	ab := []int{b[0] - a[0], b[1] - a[1]}
	bc := []int{b[0] - c[0], b[1] - c[1]}
	if ab[0]*bc[1] != ab[1]*bc[0] {
		return true
	}
	return false

}
func TestVounter() {
	docker := 0
	volunter := 0
	docker = 5
	volunter = 6
	arr := []int{60, 100, 200, 300, 600}

	//for i:=1; i<=docker; i++ {
	//	t := 0;
	//	fmt.Scan(&t)
	//	arr = append(arr,t)
	//}
	sort.Ints(arr)

	if volunter >= docker {
		more := volunter - docker
		for i := docker; i > 0; i-- {
			if more <= 0 {
				break
			}

			if more >= 3 {
				arr[i] = arr[i]/10*3 + arr[i]
				more -= 3
			} else if more >= 2 {
				arr[i] = arr[i]/10*2 + arr[i]
				more -= 2
			} else {
				arr[i] = arr[i]/10*1 + arr[i]
				more -= 1
			}
		}
	} else {
		less := docker - volunter

		for i := volunter; i > less; i-- {
			if arr[i]/10*3-arr[less]/10*2 > 0 {
				arr[i] = arr[i]/10*3 + arr[i]
				less++
			}
		}

		for j := less; j > 0; j-- {
			arr[j] = arr[j] - arr[j]/10*2
		}
	}
	result := 0
	for _, v := range arr {
		result += v
	}
	fmt.Println(result)

}

func TestNum() {
	arr := []int{129, 129, 130, 130}
	a, b, c, d := arr[0]-128, arr[1]-128, arr[2]-128, arr[3]-128
	//temp := (float64(a+b+c+d)/4.0 )
	temp, _ := strconv.ParseFloat(fmt.Sprintf("%.5f", float64(a+b+c+d)/4.0), 64) // 保留5位小数

	num := int(math.Ceil(temp))

	result := 0 - num
	fmt.Println(result)
}

func Calc(index string, a, b int) int {
	ret := a + b
	fmt.Println(index, a, b, ret)
	return ret
}

type People interface {
	Speak(string) string
}

type Stduent struct {
}

func (stu *Stduent) Speak(think string) (talk string) {
	if think == "bitch" {
		talk = "Youare a good boy"
	} else {
		talk = "hi"
	}
	return
}

func TestFunc() []func() {
	var funs []func()
	for i := 0; i < 2; i++ {
		funs = append(funs, func() {
			println(&i, i)
		})
	}
	return funs
}

//1002. 查找共用字符
func CommonChars(words []string) (ans []string) {
	minFreq := [26]int{}
	for i := range minFreq {
		minFreq[i] = math.MaxInt64
	}
	for _, word := range words {
		freq := [26]int{}
		for _, b := range word {
			freq[b-'a']++
		}
		for i, f := range freq[:] {
			if f < minFreq[i] {
				minFreq[i] = f
			}
		}
	}
	for i := byte(0); i < 26; i++ {
		for j := 0; j < minFreq[i]; j++ {
			ans = append(ans, string('a'+i))
		}
	}
	return
}

//812:最大三角形面积
func LargestTriangleArea(points [][]int) float64 {
	N := len(points)
	var res float64
	for i := 0; i < N-2; i++ {
		for j := i + 1; j < N-1; j++ {
			for k := j + 1; k < N; k++ {
				point1 := points[i]
				point2 := points[j]
				point3 := points[k]
				x1, y1 := point1[0], point1[1]
				x2, y2 := point2[0], point2[1]
				x3, y3 := point3[0], point3[1]
				res = math.Max(res, 0.5*math.Abs(float64(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))))
			}
		}
	}
	fmt.Println(res)
	return res
}

//997. 找到小镇的法官
func findJudge(n int, trust [][]int) int {
	arr := make([]int, n+1)
	for _, v := range trust {
		arr[v[0]]--
		arr[v[1]]++
	}
	for i := 1; i <= n; i++ {
		if arr[i] == n-1 {
			return i
		}
	}
	return -1
}

//867. 转置矩阵
func Transpose(matrix [][]int) [][]int {
	n, m := len(matrix), len(matrix[0])
	t := make([][]int, m)

	for i := range t {
		t[i] = make([]int, n)
		for j := range t[i] {
			t[i][j] = -1
		}
	}

	for i, row := range matrix {
		for j, v := range row {
			t[j][i] = v
		}
	}
	return t

}

//976. 三角形的最大周长
func LargestPerimeter(nums []int) int {
	sort.Ints(nums)
	for i := len(nums) - 1; i >= 2; i-- {
		if nums[i-2]+nums[i-1] > nums[i] {
			return nums[i] + nums[i-1] + nums[i-2]
		}
	}
	return 0

}

//967. 连续差相同的数字 //todo:5月13未解出
func NumsSameConsecDiff(n int, k int) []int {
	cur := make(map[int]int)

	for i := 1; i <= 9; i++ {
		cur[i] = i
	}

	for i := 1; i <= n-1; i++ {
		cur2 := make(map[int]int)
		for key, v := range cur {
			d := v % 10
			if d-k >= 0 {
				cur2[key] = 10*v + d - k
			}
			if d+k <= 9 {
				cur2[key] = 10*v + d + k
			}
		}
		cur = cur2
	}
	fmt.Println(cur)
	if n == 1 {
		return []int{0}
	}
	arr := make([]int, len(cur))
	t := 0
	for _, x := range cur {
		arr[t] = x
		t++
	}
	return arr
}

func HeightChecker(heights []int) int {
	//tempArr := make([]int,len(heights))
	//for k,v := range heights {
	//	tempArr[k] = v
	//}
	tempArr := append([]int{}, heights...) //复制数组

	sort.Ints(heights)
	ans := 0
	for i := 0; i < len(heights); i++ {
		if heights[i] != tempArr[i] {
			ans++
		}
	}
	return ans
}

//1431. 拥有最多糖果的孩子
func KidsWithCandies(candies []int, extraCandies int) []bool {
	tempArr := append([]int{}, candies...)
	sort.Ints(candies)
	maxNum := candies[len(candies)-1]
	arr := make([]bool, len(candies))

	for k, v := range tempArr {
		if (v + extraCandies) >= maxNum {
			arr[k] = true
		} else {
			arr[k] = false
		}
	}
	return arr

}

func TestCopySlice() {
	slice1 := []int{1, 2, 3, 4, 5}
	slice2 := []int{5, 4, 3}
	copy(slice2, slice1)
	fmt.Println(slice2)

}

//804. 唯一摩尔斯密码词
func UniqueMorseRepresentationsBob(words []string) int {
	var flagArr = make(map[byte]string)
	var arr = []string{".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."}

	var char byte
	char = 97
	for _, password := range arr {
		flagArr[char] = password
		char += 1
	}

	var resultMap = make(map[string]bool)
	for _, word := range words {
		var wordString string
		for _, character := range word {
			s1 := flagArr[byte(character)]
			wordString = fmt.Sprintf("%s%s", wordString, s1)
		}
		resultMap[wordString] = true

	}

	return len(resultMap)

}

var morse = []string{".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."}

func UniqueMorseRepresentations(words []string) int {
	set := map[string]struct{}{}
	for _, word := range words {
		trans := &strings.Builder{}
		for _, ch := range word {
			trans.WriteString(morse[ch-'a'])
		}
		set[trans.String()] = struct{}{}
	}
	return len(set)
}

//58:最后一个单词的长度
func LengthOfLastWord(s string) int {
	end := len(s) - 1
	if end == 0 {
		return 1
	}
	for end >= 0 && s[end] == ' ' {
		end--
	}
	if end < 0 {
		return 0
	}
	var start = end
	for start >= 0 && s[start] != ' ' {
		start--
	}
	return end - start
}

//14. 最长公共前缀
func LongestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}
	var ans = strs[0]

	for i := 1; i < len(strs); i++ {
		var j = 0
		for ; j < len(ans) && j < len(strs[i]); j++ {
			if ans[j] != strs[i][j] {
				break
			}
		}
		ans = ans[0:j]
		if ans == "" {
			return ans
		}
	}
	return ans
}

func DetectCapitalUse(word string) bool {
	s1 := strings.ToLower(word)
	s2 := strings.ToUpper(word)
	c := word[0]
	if c > 'a' {
		c = c - 32
	}
	s3 := fmt.Sprintf("%c%s", c, strings.ToLower(word[1:]))
	return word == s1 || word == s2 || word == s3
}

func StrStr(haystack string, needle string) int {
	nLen := len(needle)
	for i := 0; i < len(haystack)-nLen+1; i++ {
		temp := haystack[i : i+nLen]
		if needle == temp {
			return i
		}
	}
	return -1
}

//151. 反转字符串中的单词
func ReverseWords(s string) string {
	words := strings.Split(s, " ")
	var filter []string
	for _, str := range words {
		if str != "" {
			filter = append(filter, str)
		}
	}

	for i, j := 0, len(filter)-1; i < j; i, j = i+1, j-1 {
		filter[i], filter[j] = filter[j], filter[i]
	}
	return strings.Join(filter, " ")

}

//42 接雨水
func trap(height []int) int {
	var sum int
	for i := 1; i < len(height)-1; i++ {
		maxLeft, maxRight := 0, 0
		for j := i - 1; j >= 0; j-- {
			if height[j] > maxLeft {
				maxLeft = height[j]
			}
		}
		for k := i + 1; k < len(height); k++ {
			if height[k] > maxRight {
				maxRight = height[k]
			}
		}
		min := Min(maxLeft, maxRight)
		if min > height[i] {
			sum += min - height[i]
		}
	}
	return sum
}

//42 接雨水 动态规划
func trap2(height []int) int {
	var sum int
	maxLeft := make([]int, len(height))
	maxRight := make([]int, len(height))
	for i := 1; i < len(height)-1; i++ {
		maxLeft[i] = Max(maxLeft[i-1], height[i-1])
	}
	for i := 1; i < len(height)-2; i++ {
		maxRight[i] = Max(height[i+1], height[i+1])
	}

	for i := 1; i < len(height)-1; i++ {
		min := Min(maxLeft[i], maxRight[i])
		if min > height[i] {
			sum += height[i]
		}
	}
	return sum
}

//125 验证回文串
func IsPalindrome(s string) bool {
	s = strings.ToLower(s)
	var sl []byte
	for i := 0; i < len(s); i++ {
		if isalnum(s[i]) {
			sl = append(sl, s[i])
		}
	}
	length := len(sl)
	for j := 0; j < length/2; j++ {
		if sl[j] != sl[length-1-j] {
			return false
		}
	}
	return true
}

func isalnum(ch byte) bool {
	return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')
}

//135 分发糖果
func Candy(ratings []int) int {
	left := make([]int, len(ratings))
	right := make([]int, len(ratings))
	for i := 0; i < len(ratings); i++ {
		left[i], right[i] = 1, 1
	}
	for i := 1; i < len(ratings); i++ {
		if ratings[i] > ratings[i-1] {
			left[i] = left[i-1] + 1
		}
	}
	var count = left[len(ratings)-1]
	for i := len(ratings) - 2; i >= 0; i-- {
		if ratings[i] > ratings[i+1] {
			right[i] = right[i+1] + 1
		}
		count += Max(left[i], right[i])
	}
	return count
}

//22 括号生成
func generateParenthesis(n int) []string {
	var res []string
	generateHelper(&res, "", n, n)
	return res

}
func generateHelper(res *[]string, str string, left int, right int) {
	if left == 0 && right == 0 {
		*res = append(*res, str)
		return
	}
	if left == right {
		generateHelper(res, str+"(", left-1, right)
	} else if left < right {
		if left > 0 {
			generateHelper(res, str+"(", left-1, right)
		}
		generateHelper(res, str+")", left, right-1)
	}
}

//172. 阶乘后的零
func trailingZeroes(n int) int {
	var count = 0
	for n > 0 {
		count += n / 5
		n = n / 5
	}
	return count
}

//392. 判断子序列
func IsSubsequence(s string, t string) bool {
	n, m := len(s), len(t)
	i, j := 0, 0
	for i < n && j < m {
		if s[i] == t[j] {
			i++
		}
		j++
	}
	return i == j
}

func minimumTotal(triangle [][]int) int {
	n := len(triangle)
	f := make([][]int, n)
	for i := 0; i < n; i++ {
		f[i] = make([]int, n)
	}
	f[0][0] = triangle[0][0]
	for i := 1; i < n; i++ {
		f[i][0] = f[i-1][0] + triangle[i][0]
		for j := 1; j < i; j++ {
			f[i][j] = Min(f[i-1][j-1], f[i-1][j]) + triangle[i][j]
		}
		f[i][i] = f[i-1][i-1] + triangle[i][i]
	}
	ans := math.MaxInt32
	for i := 0; i < n; i++ {
		ans = Min(ans, f[n-1][i])
	}
	return ans
}

//167.两数之和II
func twoSumSelf(numbers []int, target int) []int { //自己写的暴力解法
	var result []int
	for i := 0; i < len(numbers)-1; i++ {
		temp := numbers[i]
		for j := i + 1; j < len(numbers); j++ {
			if temp+numbers[j] == target {
				result = []int{i, j}
				return result
			}
		}
	}
	return result
}

//167.两数之和II  二分查找法
func twoSum2(numbers []int, target int) []int {
	for i := 0; i < len(numbers); i++ {
		low, high := i+1, len(numbers)-1
		for low <= high {
			mid := (high-low)/2 + low
			if numbers[mid] == target-numbers[i] {
				return []int{i + 1, mid + 1}
			} else if numbers[mid] > target-numbers[i] {
				high = mid - 1
			} else {
				low = mid + 1
			}
		}
	}
	return []int{-1, -1}
}

//两数之和II 双指针解法
func twoSum3(numbers []int, target int) []int {
	low, high := 0, len(numbers)-1
	for low < high {
		sum := numbers[low] + numbers[high]
		if sum == target {
			return []int{low + 1, high + 1}
		} else if sum < target {
			low++
		} else {
			high--
		}
	}
	return []int{-1, -1}
}

//39 组合总数 回溯  看不懂
func CombinationSum(candidates []int, target int) (ans [][]int) {
	comb := []int{}
	var dfs func(target, idx int)
	dfs = func(target, idx int) {
		if idx == len(candidates) {
			return
		}
		if target == 0 {
			ans = append(ans, append([]int(nil), comb...))
			return
		}
		// 直接跳过
		dfs(target, idx+1)
		// 选择当前数
		if target-candidates[idx] >= 0 {
			comb = append(comb, candidates[idx])
			dfs(target-candidates[idx], idx)
			comb = comb[:len(comb)-1]
		}
	}
	dfs(target, 0)
	return
}

//11. 盛最多水的容器
func MaxArea2(height []int) int {
	l, r := 0, len(height)-1
	ans := 0
	for l < r {
		areas := Min(height[l], height[r]) * (r - l)
		ans = Max(ans, areas)
		if height[l] <= height[r] {
			l++
		} else {
			r--
		}
	}
	return ans
}

// blank 返回长度为 n 的由空格组成的字符串
func blank(n int) string {
	return strings.Repeat(" ", n)
}

//68. 文本左右对齐
func fullJustify(words []string, maxWidth int) (ans []string) {
	right, n := 0, len(words)
	for {
		left := right // 当前行的第一个单词在 words 的位置
		sumLen := 0   // 统计这一行单词长度之和
		// 循环确定当前行可以放多少单词，注意单词之间应至少有一个空格
		for right < n && sumLen+len(words[right])+right-left <= maxWidth {
			sumLen += len(words[right])
			right++
		}

		// 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格
		if right == n {
			s := strings.Join(words[left:], " ")
			ans = append(ans, s+blank(maxWidth-len(s)))
			return
		}

		numWords := right - left
		numSpaces := maxWidth - sumLen

		// 当前行只有一个单词：该单词左对齐，在行末填充剩余空格
		if numWords == 1 {
			ans = append(ans, words[left]+blank(numSpaces))
			continue
		}

		// 当前行不只一个单词
		avgSpaces := numSpaces / (numWords - 1)
		extraSpaces := numSpaces % (numWords - 1)
		s1 := strings.Join(words[left:left+extraSpaces+1], blank(avgSpaces+1)) // 拼接额外加一个空格的单词
		s2 := strings.Join(words[left+extraSpaces+1:right], blank(avgSpaces))  // 拼接其余单词
		ans = append(ans, s1+blank(avgSpaces)+s2)
	}
}

//209 长度最小的子数组
func minSubArrayLen(s int, nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	ans := math.MaxInt32
	start, end := 0, 0
	sum := 0
	for end < n {
		sum += nums[end]
		for sum >= s {
			ans = Min(ans, end-start+1)
			sum -= nums[start]
			start++
		}
		end++
	}
	if ans == math.MaxInt32 {
		return 0
	}
	return ans
}

//3.无重复字符的最长子串
func LengthOfLongestSubstring(s string) int {
	if len(s) == 0 {
		return 0
	}
	charMap := make(map[byte]int)
	left, max := 0, 0
	for i := 0; i < len(s); i++ {
		_, ok := charMap[s[i]]
		if ok {
			left = Max(left, charMap[s[i]]+1)
		}
		charMap[s[i]] = i
		max = Max(max, i-left+1)
	}
	return max
}

//383.赎金信
func canConstruct(ransomNote string, magazine string) bool {
	if len(ransomNote) > len(magazine) {
		return false
	}
	rMap := make(map[byte]int)
	for i := 0; i < len(ransomNote); i++ {
		rMap[ransomNote[i]] += 1
	}
	for i := 0; i < len(magazine); i++ {
		_, ok := rMap[magazine[i]]
		if ok {
			rMap[magazine[i]] -= 1
		}
	}
	for _, v := range rMap {
		if v > 0 {
			return false
		}
	}
	return true
}

//30.串联所有单词的子串
func FindSubstring(s string, words []string) []int {
	var res []int
	if len(s) == 0 || len(words) == 0 {
		return res
	}
	oneWord := len(words[0])
	wordNum := len(words)
	firstMap := make(map[string]int)
	for _, v := range words {
		firstMap[v] += 1
	}
	for i := 0; i < oneWord; i++ {
		left, right, count := i, i, 0
		temMap := make(map[string]int)
		for right+oneWord <= len(s) {
			w := s[right : right+oneWord]
			right += oneWord
			if _, ok := firstMap[w]; !ok {
				count = 0
				left = right
				temMap = make(map[string]int)
			} else {
				temMap[w] += 1
				count++
				for temMap[w] > firstMap[w] {
					tw := s[left : left+oneWord]
					count--
					temMap[tw]--
					left += oneWord
				}
				if count == wordNum {
					res = append(res, left)
				}
			}
		}
	}
	return res
}

//76.最小覆盖子串
func minWindow(s string, t string) string {
	ori, cnt := make(map[byte]int), make(map[byte]int)
	for i := 0; i < len(t); i++ {
		ori[t[i]] += 1
	}
	sLen := len(s)
	ansL, ansR := -1, -1
	length := math.MaxInt32
	check := func() bool {
		for k, v := range ori {
			if cnt[k] < v {
				return false
			}
		}
		return true
	}
	for l, r := 0, 0; r < sLen; r++ {
		if r < sLen && ori[s[r]] > 0 {
			cnt[s[r]] += 1
		}
		for check() && l <= r {
			if r-l+1 < length {
				length = r - l + 1
				ansL, ansR = l, l+length
			}
			if _, ok := ori[s[l]]; ok {
				cnt[s[l]] -= 1
			}
			l++
		}
	}
	if ansL == -1 {
		return ""
	}
	return s[ansL:ansR]
}

//54.螺旋矩阵
func SpiralOrder(matrix [][]int) []int {
	if len(matrix) == 0 {
		return []int{}
	}
	l, r, t, b := 0, len(matrix[0])-1, 0, len(matrix)-1
	var res []int
	for {
		for i := l; i <= r; i++ {
			res = append(res, matrix[t][i])
		}
		t++
		if t > b {
			break
		}
		for i := t; i <= b; i++ {
			res = append(res, matrix[i][r])
		}
		r--
		if l > r {
			break
		}
		for i := r; i >= l; i-- {
			res = append(res, matrix[b][i])
		}
		b--
		if t > b {
			break
		}
		for i := b; i >= t; i-- {
			res = append(res, matrix[i][l])
		}
		l++
		if l > r {
			break
		}
	}
	return res
}

//73.矩阵置零
func setZeroes(matrix [][]int) {
	row := make([]bool, len(matrix))
	col := make([]bool, len(matrix[0]))
	for i, r := range matrix {
		for j, v := range r {
			if v == 0 {
				row[i] = true
				col[j] = true

			}
		}
	}

	for i, r := range matrix {
		for j, _ := range r {
			if row[i] || col[j] {
				matrix[i][j] = 0
			}
		}
	}

}

//205.同构字符串
func isIsomorphic(s string, t string) bool {
	s2t := make(map[byte]byte)
	t2s := make(map[byte]byte)
	for i:=0; i<len(s); i++ {
		a,b := s[i], t[i]
		if s2t[a] !=0 && s2t[a] != b || t2s[b]!=0 && t2s[b] !=a {
			return false
		}
		s2t[a] = b
		t2s[b] = a
	}
	return true
}

//290.单词规律
func wordPattern(pattern string, s string) bool {
	s2t := make(map[byte]string)
	t2s := make(map[string]byte)
	sArr := strings.Split(s, " ")
	if len(pattern) != len(sArr) {
		return false
	}
	for i:=0; i<len(pattern); i++ {
		a,b := pattern[i],sArr[i]
		if s2t[a]!= "" && s2t[a] != b || t2s[b]>0 && t2s[b]!=a {
			return false
		}
		s2t[a] = b
		t2s[b] = a
	}
	return true

}